import java.awt.image.AreaAveragingScaleFilter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.stream.Collectors;

/**
 * @description:
 * @Author: wuzhenbin
 * @CreateTime: 2025-02-14
 */
public class leetcode_56 {
    public static void main(String[] args) {
        // int[][] ints = {{1, 4}, {0, 2}, {3, 5}};
        int[][] ints = {{1, 3}, {2, 6}, {8, 10}};
        //int[][] ints = {{1, 4}, {5, 6}};
        System.out.println(Arrays.deepToString(merge1(ints)));
    }


    //失败的算法
    public static int[][] merge(int[][] intervals) {
        ArrayList<int[]> list = new ArrayList<>();
        if (intervals.length == 1) return intervals;
        for (int i = 0; i < intervals.length - 1; i++) {
            while (i < intervals.length - 1 && judge(intervals[i], intervals[i + 1]) != null) {
                //list.add(judge(intervals[i], intervals[i + 1]));
                intervals[i + 1] = judge(intervals[i], intervals[i + 1]);
                i++;
            }
            list.add(intervals[i]);
            if (i < intervals.length - 1) {
                list.add(intervals[i]);
                list.add(intervals[i + 1]);
            }
            i++;
        }
        //注意这里的转换方法!!!! 输入一个new构造方法
        return list.stream().toArray(int[][]::new);
    }

    private static int[] judge(int[] nums1, int[] nums2) {
        if ((nums1[1] >= nums2[0] && nums1[0] <= nums2[1]) || (nums1[0] >= nums2[0] && nums1[1] <= nums2[1])) {
            int[] ints = new int[2];
            ints[0] = Math.min(nums1[0], nums2[0]);
            ints[1] = Math.max(nums1[1], nums2[1]);
            return ints;
        }
        return null;
    }

    /**
     * 你在使用 Arrays.stream(intervals).sorted(new Comparator<int[]>() {...}) 时遇到排序不生效的原因是，你使用了 stream()，但是排序并不会修改原始数组 intervals，因为 stream() 返回的是一个新的流，并且 sorted() 返回的是一个 排序后的流，而不是直接修改原始数组。
     * <p>
     * 解决方法：
     * 你应该 直接使用 Arrays.sort() 来排序原始数组，而不是使用流（stream()）。这样可以直接对原始数组进行排序。
     * 如果你想要使用流并保持 stream() 的方法，可以使用 .toArray() 将排序后的流转换回数组。
     * 方法 1：使用 Arrays.sort()（推荐）
     * java
     * 复制
     * Arrays.sort(intervals, new Comparator<int[]>() {
     *
     * @param intervals
     * @return
     * @Override public int compare(int[] o1, int[] o2) {
     * return o1[0] - o2[0]; // 比较区间的起始值
     * }
     * });
     * 或者使用 Lambda 表达式：
     * <p>
     * java
     * 复制
     * Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
     * 方法 2：使用 stream()，并返回排序后的结果
     * java
     * 复制
     * intervals = Arrays.stream(intervals)
     * .sorted((o1, o2) -> o1[0] - o2[0])
     * .toArray(int[][]::new);
     * 这里，sorted() 将返回一个新的排序后的流，然后使用 toArray(int[][]::new) 将流转换回二维数组。
     * <p>
     * 为什么 Arrays.sort() 更适合？
     * Arrays.sort() 会直接修改原始数组的顺序，而 stream() 返回的是一个新的流，它不会修改原始数组。
     * <p>
     * 总结：
     * 如果你只需要排序原始数组，建议使用 Arrays.sort()，它是直接修改原始数组并且更为高效。如果你更倾向于使用 stream()，则需要记住流操作会生成新的数据结构，不会修改原始数组，因此需要使用 toArray() 返回排序后的数组。
     */
    //失败的解法
    public static int[][] merge1(int[][] intervals) {
        if (intervals.length == 1) return intervals;
        //注意Arrays.sort  和Arrays.stream(intervals).sorted() 的区别!!!!!!!
        //对于数组排序  直接用Arrays.sort方法
        //Arrays.sort  是在原数组的基础上进行排序!!但是像用开启流的方式写的话 是另外开启一个流 不是在原基础上得到的  想得到数据  需要用Collect收集器收集成一个另外的list
        //Arrays.stream(intervals).sorted()
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        ArrayList<int[]> list = new ArrayList<>();
        int index = 1;
        ArrayList<Integer> tmp = new ArrayList<>();
        boolean[] mark = new boolean[intervals.length];
        while (index < intervals.length + 1) {
            int first = index - 1;
            while (index < intervals.length && intervals[index - 1][1] <= intervals[index][1] && intervals[index - 1][1] >= intervals[index][0]) {
                mark[index - 1] = true;
                mark[index] = true;
                index++;
            }

            if (first == index - 1) {
                if (mark[first] = true) list.add(intervals[index]);
                else list.add(intervals[first]);
                index++;
            } else list.add(new int[]{intervals[first][0], intervals[index - 1][1]});
        }


        return list.stream().toArray(int[][]::new);
    }


    //感想:  对于这种问题 用一个哨兵保存值  不要陷在指针里面出不来  直接让这个哨兵 处理多重字串的状态
    public static int[][] merge2(int[][] intervals) {
        if (intervals.length == 1) return intervals;

        // 排序，按区间的起始值排序
        Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));

        ArrayList<int[]> list = new ArrayList<>();
        // 使用两个变量来控制合并的区间
        int[] currentInterval = intervals[0];  // 第一个区间初始化为当前区间

        for (int i = 1; i < intervals.length; i++) {
            // 如果当前区间与下一个区间重叠
            if (currentInterval[1] >= intervals[i][0]) {
                // 合并区间：更新当前区间的结束位置
                currentInterval[1] = Math.max(currentInterval[1], intervals[i][1]);
            } else {
                // 如果不重叠，将当前区间添加到结果列表
                list.add(currentInterval);
                // 更新当前区间为下一个区间
                currentInterval = intervals[i];
            }
        }

        // 最后一个区间需要添加到结果列表
        list.add(currentInterval);

        // 返回合并后的区间数组
        return list.toArray(new int[list.size()][]);
    }


}
